package Real19;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
//重点看自己写出来的，数组对应的方法，数组对应 可以给单个索引赋予多维的含义；这个角度思考问题就会很简单，从表达上也可以使用map来实现，一个key对应多维的含义(可以用Map集合做value来表示多维含义)；
// OFFSET和DIRECTION; howTo和pathpre;是两对儿对应数组；
public class Maze {

	private static final boolean OK = true, NOT = false;
	private static final int R = 30, C = 50;
	private static final int[][] OFFSET = { {1,0}, {0,-1}, {0,1}, {-1,0} };   //让孩子和方向对应；
	private static final char[] DIRECTION = { 'D', 'L', 'R', 'U' };  //根据需求调整为字典序小的优先，这样就会得到bfs中字典序最小的那个path；
	private static boolean[] visited = new boolean[R * C];   //防止重复访问。如果构建成图的话，还可以分辨不同连通分量；
	private static char[] howTo = new char[R * C];  //朝什么方向到的当前编号；和记录父亲节点的数组对应，就知道父亲节点是沿着什么方向到的该索引编号；
	private static int[] pathpre = new int[R * C];  //索引节点来自哪个编号的节点； 记录每个节点的父节点，这样就可以顺藤摸瓜找到path；
																//(因为邻接点间不考虑平行路径，且有环时只访问一遍(有visited)，所以不存在父节点被覆盖重写，况且数组里只能存一个父亲节点，即使是覆盖了也是唯一确定的)
	
	public static void main(String[] args) throws FileNotFoundException {
		
		boolean[][] maze = new boolean[R][C];
		
		Scanner sc = new Scanner(new File("maze.txt"));
		
		for (int i = 0; i < R; i++) {     //对矩阵进行存储时，按照语意建立二维数组并按照语意初始化即可，不用管是行还是列， 因为访问的时候是按照语意访问的；
			String way = sc.next();  //除了nextLine是直接读一行，其余都是从第一个有效字符(非结束符)开始读，遇到结束符(空格回车)停止；
			
			for(int j = 0; j < C; j++) {
				if(way.charAt(j) == '0')  //charAt不能直接和0比较，要么-0；要么和'0'
					maze[i][j] = OK;    //从0开始的一维编号，转成从0开始的二维坐标；
				else
					maze[i][j] = NOT;
				
			}
		}
		
		Arrays.fill(visited, false);
		Arrays.fill(howTo, 'x');
		Arrays.fill(pathpre, 1, pathpre.length, -1);    //快速初始化数组；注意带范围的这种方式，是左闭右开的；
		
		ArrayList<Character> ans = bfs(maze, 0); //按道理，给bfs传入 起点、终点、maze 即可
		String s = "";
		for (Character c : ans) {
			s += c;
		}
		
		System.out.println(s);
//		System.out.println(ans);                 // 注释掉的二者是等价的；
//		System.out.println(Arrays.toString(ans.toArray()));
		System.out.println("end");

	}

	//bfs从0处开始寻找出口，返回路径；
	private static ArrayList<Character> bfs(boolean[][] maze, int source) {

		Queue<Integer> q = new LinkedList<>(); //语意可以定为：访问队列。入队叫visited，*而出队是 开始访问节点的孩子*；而当前节点早已经该被visited了，也就是说入队就叫visited；
		q.add(source);
		visited[source] = true;   
		
		while( !q.isEmpty() ) {		//访问队列不为空，就一直出队进行遍历；
			int now = q.remove();
//			visited[now] = true;   //在实际情况中，只要入队了就算是访问过了，应该立刻设置visited=true，这一题就是在这里翻车了！；否则顺序得不到保证，虽然就bfs本身而言，pre可能被覆盖 也是被同深度的其他节点覆盖，bfs不会错。但是这样就失去了部分实际意义；
			
			//TODO:adjacents一维编号
			ArrayList<Integer[]> nexts = getNexts(now);
			
			int index = 0; //index用来辅助foreach 方便拿到索引
			for (Integer[] e : nexts) {     //TODO：空指针异常
				
				int nextX = e[0];   
				int nextY = e[1];
				int linear = nextX * C + nextY; //判断完合法性之后再转换成 线性坐标；
				if(nextX>=0 && nextX<R && nextY>=0 && nextY<C) {
					
					if(maze[nextX][nextY] == OK && !visited[linear]) {
						howTo[linear] = DIRECTION[index]; 
						pathpre[linear] = now;

						//version3:基于V2的改进，在DIRECTION上动手！！
						//version1 + DIRECTION
						if(linear == R*C-1)  
							break;
						else { 
							q.add(linear);     //如果不在入队时设为visited，事实证明：可能会出现再次访问，覆盖pre并重复入队的情况，如果对具体路径有要求，可能会导致路径和预期的不一致。但不影响bfs的路径最短性质；
							visited[linear] = true;   //因为now节点的下一层节点入队的时候队列可能不是空的，如果图中有环，上一层的某个节点出队时可能也会访问到当前队列里的某个节点，但是这时候那个节点还没到队首 visited仍然是false，因此会被二次访问；
						}
						
						//version1:不符合需求；
//						if(linear == R*C-1)    //这样的写法只能得到第一次成功的那条路径，因为第一次找到出口的时候就直接break了；
//							break;
//						else 
//							q.add(linear);     //容器里占位得用一维坐标，方便；

						//version2:行不通；
//						if(linear == R*C-1) {    //想获得全部可能的路径就得把所有可能遍历一遍。。即让q为空时自己结束即可，在这之前每次找到出口就做个标记 然后重置状态，即装作没找到再拐回去；
//							paths.add(getPath()); //做标记
//							//TODO:但是没办法重置状态。。因为一路下来经过的所有节点都变成 被访问过了，又不是递归还有占位锚点。。现在没法回去；所以行不通；
//							// 需求表达的意思是：bfs得到的最短路径有多条，让找到字典序最小的那个。但换个角度想，我可以直接在bfs的时候，让字典序小的方向(DIRECTION)优先不就好了！！！
//						}
//						else
//							q.add(linear);
					}
				}
			index++; //在foreach结束时++肯定没问题；
			}
		}
		return getPath();
	}

	private static ArrayList<Character> getPath() { 
		ArrayList<Character> ret = new ArrayList<>();
		
		int cur = R * C - 1;
		
		while( cur != 0 ) {
			ret.add( howTo[cur] );
			cur = pathpre[cur];
		} //0退出来正好，因为记的是朝向；

		Collections.reverse(ret);
		return ret;
	}

	private static ArrayList<Integer[]> getNexts(int now) {
		int X = now / C;  //坐标转换要千万小心，不需要R，需要的是每行多少个；
		int Y = now % C;
		ArrayList<Integer[]> nexts = new ArrayList<>();   //nexts数组里不应该放一维坐标；因为判断越界与否的时候，是根据二维的图来判断的，假如Y坐标出现负数，本来是越界的，但如果转换成一维坐标，50的L就变成了49，这样返回之后是无法判断合法与否的！！！
		
		for (int[] off : OFFSET) {
			nexts.add(new Integer[]{ (X+off[0]),(Y+off[1]) } );  //这里的一二维编号转换要注意；只乘了R; 此外，写计算式的时候语意一定要清楚，括号千万不能忘了带；
		}
		return nexts;
	}

}
